package exercises.newcoder.solution;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * <a href="https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=202&&tqId=38810&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC101 从上往下打印二叉树</a>
 *
 * @author or2
 * @Description 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 * @create 2021年09月12日 时间: 10:01
 */
public class WC101 {

    private static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
//        记录答案
        ArrayList<Integer> ans = new ArrayList<>();
//        输入校验
        if (root == null) {
            return ans;
        }
//        辅助双端队列 - 层序遍历
        LinkedList<TreeNode> deQue = new LinkedList<>();
        deQue.addLast(root);
        while (!deQue.isEmpty()) {
            TreeNode remove = deQue.removeFirst();
            ans.add(remove.val);
            if (remove.left != null) {
                deQue.addLast(remove.left);
            }
            if (remove.right != null) {
                deQue.addLast(remove.right);
            }
        }

        return ans;
    }
}
